/**
 * @file
 * Semantic multimap comparison.
 */

#ifndef MULTIMAP_COMPARISON_H
#define MULTIMAP_COMPARISON_H

#include<iostream>
#include<set>
#include<map>

/**
 * Multimap comparison
 * @param[in] given1 The first multiset to compare.
 * @param[in] given2 The other multiset to comare.
 * @return @c true if equal, @c false otherwise.
 */
template<class X, class Y>
  bool multimap_compare(std::multimap<X, Y> &given1, std::multimap<X, Y> &given2)
{
  // If sizes are not equal, the multimaps are trivially unequal
  if(given1.size() != given2.size())
    return false;
  
  // Storage for the co-domains of an element in the domain of the multisets
  std::multiset<Y> curr_codomain1, curr_codomain2;  

  // Storage for the previous domain elemet
  Y prev_domain_element;  

  // Iterate over both the multimaps
  typename std::multimap<X, Y>::iterator j;
  for(typename std::multimap<X, Y>::iterator i = given1.begin(),
        j = given2.begin();
      i != given1.end(),
        j != given2.end();
      i++,
        j++)
    {
      // If any domain element is unequal, the multimaps are unequal
      if (i->first != j->first)
        return false;
      
      // If the current elements are the first elements, initialize the previous element
      // and the codomains  
      if((curr_codomain1.size() == 0) && (curr_codomain1.size() == 0))
        {
          prev_domain_element = i->first;
          curr_codomain1.insert(i->second);
          curr_codomain2.insert(j->second);
        }
      else
        {
          // Condition where the current domain element is different from the previous
          if (prev_domain_element != i->first)
            {
              // Compare the collected codomains, if unequal, the multimaps are unequal 
              if (curr_codomain1 != curr_codomain2)
                return false;

              // Clear the codomains
              curr_codomain1.erase(curr_codomain1.begin(), curr_codomain1.end());
              curr_codomain2.erase(curr_codomain2.begin(), curr_codomain2.end());

              // Initialise the previous domain element and the codomains
              prev_domain_element = i->first;
              curr_codomain1.insert(i->second);
              curr_codomain2.insert(j->second);
            }
          // Condition where the current domain element is the same as the previous
          else
            {
              // Add the codomain elemets to the codomains
              curr_codomain1.insert(i->second);
              curr_codomain2.insert(j->second);
            }
        }
    }
  // Iteration over the multimaps complete, no differences found
  return true;
}

#endif // MULTIMAP_COMPARISON_H
